18 December 2001: See final version of this paper:

http://www.star-lab.com/sander/spdrm/papers.html

19 November 2001. Thanks to Scott Crosby.

Original Postscript slides: http://cryptome.org/hdcp111901.ps (133KB) Verify equations below with original.

Research paper to be published when ready.

Scott Crosby crosby@qwes.math.cmu.edu :

The attacks on HDCP are neither complicated nor difficult. They are basic linear algebra. Thus, there have been at least four independent discoveries of these flaws. The four I know of are my co-authors on this presentation; Neils Ferguson; Keith Irwin

http://www.angelfire.com/realm/keithirwin/HDCPAttacks.html

and myself

http://www.cryptome.org/hdcp-weakness.htm

Keith Irwin's and my attacks have been available publically for 3 months and 3 weeks prior to Neils Ferguson's declaration. Neils' declaration and the Skylarov case were eye-openers and made me fully realize what I had done, what negative consequences I was in danger of experiencing, and what wrathful gods one risks angering by a 20-minute straightforward application of 40-year-old-math. This was an accident, not a habit. Like other researchers, I do not want to be smitten and thus do not expect to analyze any more such schemes as long as the DMCA exists in its current form.

(This statement is my own and does not represent the opinions of my co-authors.)

[11 slides.]

Scott Crosby: Cryptoanalysis of the HDCP key exchange protocol            November 9, 2001

A Cryptanalysis of the High-bandwidth Digital
Content Protection System

PRESENTED AT ACM-CCS8 DRM WORKSHOP 11/5/2001

Scott Crosby
Carnegie Mellon University

Ian Goldberg
Zero Knowledge Systems

Robert Johnson   Dawn Song   David Wagner
University of California at Berkeley

What is HDCP?

High bandwidth Digital Content Protection (HDCP) is a system for preventing access to plaintext video data sent over Digital Visual Interface (DVI). Any technique that allows access to the plaintext data is considered breaking the system.

I show that with the public and private keys from 40 devices and O(40²) work I can violate the design requirement -- I can access the plaintext. Furthermore, with the 40 sets of keys and at most O(2⁴⁰) offline work I can usurp the central authority completely.

The authentication process used in HDCP

The private key consists of a vector of 40 56-bit numbers.

The public key consists of a vector of 40 bits, half zero, half one.

Each device A, B, Bⁱ has these keys assigned by a central authority.

Dot products are computed in the ring Z/2⁵⁶Z.

The shared secret K_shared is reused later in the protocol.

The flaw

HDCP uses a linear system for generating the shared secret.

^->A_public · ^->B_private = K_shared ^?= K_{shared' =} ^->B_public · A_private

The flaw is that any device whose public key is a linear combination of public keys of other devices will, when assigned a private key that's a similar linear combination of the other devices private keys, successfully authenticate.

This flaw is fundamental, and cannot be worked around.

Proof of the break

I assume we have enough private keys ^->Bⁱ_private whose public keys span M C (Z/2⁵⁶Z)⁴⁰ , the module generated by all public keys assigned by the central authority. I assume that all of these devices will successfully authenticate with A.

As the subspace is 40 dimensional, a set of at most 40 keys will be enough.

Consider any device C with C_public Epsilon M whose public key and private key are any non-zero linear combination of B^k's public and private keys.

Say, ^->C_public = Sigma⁴⁰_i=1 a_i^->Bⁱ_public

And, ^->C_private = Sigma⁴⁰_i=1 a_i^->Bⁱ_private

Let A and C authenticate

K_shared = ^->A_public · ^->C_private = ^->A_public · Sigma⁴⁰_i=1 a_i^->Bⁱ_private

      = Sigma⁴⁰_i=1 a_i ⁽->A_public · ^->Bⁱ_private) = Sigma⁴⁰_i=1 a_i^->Kⁱ_shared

K_shared' = ^->C_public · ^->A_private = ^->A_private · Sigma⁴⁰_i=1 a_i^->Bⁱ_public

      = Sigma⁴⁰_i=1 a_i ⁽->A_private · ^->Bⁱ_public) = Sigma⁴⁰_i=1 a_i^->Kⁱ_shared'

When A and C authenticate

Sigma⁴⁰_i=1 = K_shared ?/= K_shared' = Sigma⁴⁰_i=1a_iKⁱ_shared'

We know that Kⁱ_shared = Kⁱ_shared' for all i because by assumption, Bⁱ's successfully authenticate with A. Therefore, Kⁱ_shared = Kⁱ_shared' and this authentication succeeds.

Thus, for any device C with in C_public Epsilon M, we can decrypt any stream in O(40²) work by rewriting ^->C_public as a linear combination of ^->Bⁱ_public.

Furthermore, we can forge keys in at most O(2⁴⁰) work by enumerating all well-formed public keys and seeing if they're in M. This completely usurps the central authority; we can do all that they can do.

In practice, I expect we can usurp the authority without this work factor.

Attacks that don't need the ability to forge

These avoid the hassle of finding well-formed public keys in M.

well-formed public keys in M . We don't have to forge to be able to clone, eavesdrop, or avoid the blacklist. We do have a ready source of well-formed public keys: All devices come with such a key, and receivers supply their public key on demand. We can masquerade as any receiver for whom we have their public key. Just sit in the middle between them and the transmitter, snarf the receivers public key, and use it as our own. This can be done in O(40²) work; by rewriting ^->C_public as a linear combination of ^->Bⁱ_public.

What about modifications? Longer key vectors?

If there are longer key vectors, the attacks continue to work, but we may not be able to forge because of the pesky well-formedness condition on public keys.

For example, they may chose a submodule where it may be hard to find a new key ^->C_public Epsilon M that is well-formed. The best general algorithm I've found for finding well-formed keys is brute-force.

A variant of this problem is in is NP-complete (reduction from subset-sum).

But, longer key vectors do not make us immune from any of my non-forging attacks. I can decrypt, clone, and avoid any blacklist.

What about modifications? How about certificates?

Modify HDCP to add cryptographic certificates onto public keys so that each device includes a digital certificate on the device's public key signed by the central authority with some conventional algorithm (e.g., RSA). The receiver sends their public key and the certificate of the public key, authentication proceeds only if the certificate is verified.

Call this protocol HDCP+certs.

This scheme is susceptible to the attacks that do not require forging.

I conjecture based on the incomplete specification available that DTCP's Restricted Authentication Protocol may be a variant of HDCP+certs. If so, this raises serious questions about its design.

Conclusion

HDCP's linear key exchange is a fundamental weaknesses. We can:

• Eavesdrop on any data

• Clone any device with only their public key

• Avoid any blacklist on devices

• Create new device keyvectors.

• In aggregate, we can usurp the authority completely.

The weaknesses are not easy to repair. Two proposed modifications are broken and still susceptible in O(n²) work and n sets of keys to:

• Eavesdrop on any data

• Clone any device with only their public key

• Avoid any blacklist on devices

Transcription and HTML by Cryptome.